package com.yanceysong.other;

public class 堆排序 {

    /**
     * 堆排序主方法
     * @param arr 待排序数组
     */
    public static void heapSort(int[] arr) {
        int n = arr.length;

        // 1. 构建最大堆：从最后一个非叶子节点开始向上调整
        // 时间复杂度：O(n) [4,6](@ref)
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 2. 排序阶段：逐个提取堆顶元素（最大值）
        for (int i = n - 1; i > 0; i--) {
            // 将当前堆顶（最大值）交换到数组末尾
            swap(arr, 0, i);
            // 调整剩余元素为最大堆（堆大小减1）
            heapify(arr, i, 0);
        }
    }

    /**
     * 堆调整（下沉操作）
     * @param arr 待调整数组
     * @param n   当前堆的有效大小
     * @param i   待调整节点的索引
     */
    private static void heapify(int[] arr, int n, int i) {
        int largest = i;       // 初始化最大值索引为当前节点
        int left = 2 * i + 1;  // 左子节点索引
        int right = 2 * i + 2; // 右子节点索引

        // 比较左子节点与当前最大值
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        // 比较右子节点与当前最大值
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }

        // 若最大值不是当前节点，则交换并递归调整
        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, n, largest); // 递归调整受影响子树[1,5](@ref)
        }
    }

    /** 交换数组元素 */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /** 测试用例 */
    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("原始数组：");
        printArray(arr);

        heapSort(arr);

        System.out.println("\n排序后数组：");
        printArray(arr);
    }

    /** 打印数组 */
    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}